﻿//LCR 105. 岛屿的最大面积
//给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
//一个 岛屿 是由一些相邻的 1 (代表土地)构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
//找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int r, int c, int& ret)
    {
        if (grid[r][c] == 0)
        {
            return;
        }
        grid[r][c] = 0;
        ret++;
        //上
        if (r - 1 >= 0) dfs(grid, r - 1, c, ret);
        //下
        if (r + 1 < grid.size()) dfs(grid, r + 1, c, ret);
        //左
        if (c - 1 >= 0) dfs(grid, r, c - 1, ret);
        //右
        if (c + 1 < grid[0].size()) dfs(grid, r, c + 1, ret);

    }
    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        int ret = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                int x = 0;
                dfs(grid, i, j, x);
                ret = max(ret, x);
            }
        }
        return ret;
    }
};